#include<bits/stdc++.h>
using namespace std;
class Node {
    public:
        Node(int val, vector<Node*> neighbors): val(val), neighbors(neighbors){}
        Node(int val): val(val){}
        int val;
        vector<Node*> neighbors;
};

// Node& graph_clone(Node& root){
//     queue<int> neighbor_node_num;
//     queue<Node&> wfs_queue;
//     Node cloned_graph;
//     int node_num = 0;
//     cloned_graph.val = root.val;
//     wfs_queue.push(cloned_graph);
//     for(auto node:root.neighbors){
//         wfs_queue.push(node);
//         node_num++;
//     }
//     neighbor_node_num.push(node_num);
//     while(!wfs_queue.empty()){
//         Node& tmp_node = wfs_queue.front();
//         wfs_queue.pop();
//         int tm_node_num = neighbor_node_num.front();
//         neighbor_node_num.pop();
//         for(int i = 0; i < tm_node_num; ++i){
//             Node& sub_node = wfs_queue.front();
//             wfs_queue.pop();
//             Node cloned_node;
//             cloned_node.val = sub_node.val;
//             tmp_node.neighbors.push_back(cloned_node);
//             node_num = 0;
//             wfs_queue.push(cloned_node);
//             for(auto node:sub_node.neighbors){
//                 wfs_queue.push(node);
//                 node_num++;
//             }
//             neighbor_node_num.push(node_num);
//         }
//     }
//     return cloned_graph;
// }

// BFS
Node* graph_cloned(Node* root) {
    map<Node* , Node*> visted;
    queue<Node*> layer_order_queue;
    // queue<Node*>
    if (root == nullptr) {
        return nullptr;
    }
    Node* cloned_node = new Node(root->val, root->neighbors);
    visted[root] = cloned_node;
    layer_order_queue.push(cloned_node);
    for(auto son_node:cloned_node->neighbors){
        layer_order_queue.push(son_node);
    }
    while(!layer_order_queue.empty()){
        Node* parent = layer_order_queue.front();
        layer_order_queue.pop();

        for(int i = 0; i < parent->neighbors.size(); ++i) {
            Node* cur_node = layer_order_queue.front();
            layer_order_queue.pop();
            if (visted.find(cur_node) != visted.end()){
                parent->neighbors[i] = visted[cur_node];
            } else {
                parent->neighbors[i] = new Node(cur_node->val, cur_node->neighbors);
                visted[cur_node] = parent->neighbors[i];
                layer_order_queue.push(parent->neighbors[i]);
                for (int j = 0; j < parent->neighbors[i]->neighbors.size(); ++j){
                    layer_order_queue.push(parent->neighbors[i]->neighbors[j]);
                }
            }
        }
    }
    return cloned_node;
}

// DFS
Node* dfs(Node* node, map<Node*, Node*>& visted){
    if (visted.find(node) != visted.end()){
        return visted[node];
    } 
    Node* new_node = new Node(node->val);
    visted[node] = new_node;
    for(int i = 0; i < node->neighbors.size(); ++i){
        new_node->neighbors.push_back(dfs(node->neighbors[i], visted));
    }
    return new_node;
}

Node* graph_cloned_dfs(Node* root) {
    map<Node*, Node*> visted;
    if (root == nullptr) {
        return nullptr;
    }
    return dfs(root, visted);
}
int main(){
    cout << sizeof(Node);
}